package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 链表的中间节点【给你单链表的头结点 head ，请你找出并返回链表的中间结点，如果有两个中间结点，则返回第二个中间结点。】
 * @date 24/5/6 22:06
 */
public class Leetcode876 {

	/*
	 * 思路分析：使用快慢指针
	 *
	 * 1、节点是奇数
	 *
	 * p1
	 * p2
	 * 1    2   3   4   5   null
	 *
	 *      p1
	 *          p2
	 * 1    2   3   4   5   null
	 *
	 *          p1
	 *                  p2
	 * 1    2   3   4   5   null
	 *
	 *
	 * 2、节点是偶数
	 *
	 * p1
	 * p2
	 * 1    2   3   4   5   6   null
	 *
	 *      p1
	 *          p2
	 * 1    2   3   4   5   6   null
	 *
	 *          p1
	 *                  p2
	 * 1    2   3   4   5   6   null
	 *
	 *              p1
	 *                          p2
	 * 1    2   3   4   5   6   null
	 *
	 */

	public static void main(String[] args) {
		ListNode head1 = ListNode.of(1, 2, 3, 4, 5);
		System.out.println(middleNode(head1));

		ListNode head2 = ListNode.of(1, 2, 3, 4, 5, 6);
		System.out.println(middleNode(head2));
	}

	private static ListNode middleNode(ListNode head) {
		ListNode p1 = head;
		ListNode p2 = head;
		while (p2 != null && p2.next != null) {
			p1 = p1.next;
			p2 = p2.next.next;
		}
		return p1;
	}
}
